package t

import (
	"fmt"
	"sort"
)

// 三数之和
func ThreeSum(nums []int) [][]int {
	res := [][]int{}
	e := len(nums)
	sort.Ints(nums)
	for i:=0; i<e; i++ {
		for j:=i+1; j<e; j++ {
			for k:=j+1; k<e; k++ {
				if nums[i] + nums[j] + nums[k] == 0 {
					tmp := []int{nums[i], nums[j] , nums[k]}
					//  去重
					if isOk(res, tmp) {
						fmt.Println(tmp)
						res = append(res, tmp)
					}
				}
			}
		}
	}

	return res
}

// 去重
func isOk(last [][]int, tmp []int) bool{
	if len(last) == 0 {
		return true
	}
	// fmt.Println(last)
	flag := 0
	for v:=0; v<len(last); v++ {
		flag = 0
		for i:=0; i<3; i++  {
			if last[v][i] == tmp[i] {
				flag++
			}else {
				break
			}
		}
		if flag == 3 {
			return false
		}
	}
	// fmt.Println(flag)

	return true
}

func ThreeSum1(nums []int) [][]int {
	res := [][]int{}
	sort.Ints(nums)
	l := len(nums)
	for i:=0; i<l; i++ {
		if (i == 0 || nums[i] != nums[i-1] ) {
			tag := -1 * nums[i]
			ls := i+1
			rs := l -1
			for (ls < rs)  {
				if nums[ls] + nums[rs] == tag {
					tmp := []int{nums[i], nums[ls] , nums[rs]}
					res = append(res, tmp)
					ls++
					rs--
					for ls < rs && nums[ls] == nums[ls-1] {
						ls++
					}
					for ls < rs && nums[rs] == nums[rs+1]  {
						rs--
					}
				}
				//大于给定值，把大值缩小
				if nums[ls] + nums[rs] > tag {
					rs--
				}
				//小于给定值，把小值加大
				if nums[ls] + nums[rs] < tag {
					ls++
				}
			}
		}
	}

	return res
}